package pers.sloera.leetcode.editor.cn;//给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。
//
// 
//
// 示例 1: 
//
// 
//输入: n = 13, k = 2
//输出: 10
//解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
// 
//
// 示例 2: 
//
// 
//输入: n = 1, k = 1
//输出: 1
// 
//
// 
//
// 提示: 
//
// 
// 1 <= k <= n <= 10⁹ 
// 
// Related Topics 字典树 👍 412 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution440 {
    public static void main(String[] args) {
        final Solution440 solution440 = new Solution440();
        final int kthNumber = solution440.findKthNumber(13, 2);
        System.out.println(kthNumber);
    }

    public int findKthNumber(int n, int k) {
        int curr = 1;
        // 索引减1
        k--;
        while (k > 0) {
            // 当前节点的所有子节点数
            int steps = getStep(curr, n);
            // k 不在当前子节点
            if (steps <= k) {
                k = k - steps;
                // 往右加一个结点
                curr++;
            } else {
                curr = curr * 10;
                // 减去curr，然后遍历curr下的子节点
                k--;
            }
        }
        return curr;
    }

    /**
     * 找root根节点的leaf下有多少个数据
     *
     * @param root 根节点
     * @param n 总数
     * @return int
     * @date 2022/3/23
     */
    private int getStep(int curr, int n) {
        int steps = 0;
        // 1 <= k <= n <= 10^9   可能溢出整数
        long first = curr;
        long last = curr;
        // 如果n是199 最后一层，是 100 101 198， 下一层的1000肯定比199大
        while (first <= n) {
            steps += Math.min(n, last) - first + 1;
            // 左右两边分别往下递归
            first = first * 10;
            last = last * 10 + 9;
        }
        return steps;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
